package leetcode.code1376;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Solution {
	public int numOfMinutes(int n, int headID, int[] manager, int[] informTime) {
		int arraySize = n;
		List<Integer>[] indexs = new ArrayList[arraySize];
		for (int i = 0; i < arraySize; i++) {
			indexs[i] = new ArrayList<>();
		}
		int root = 0;
		for (int i = 0; i < manager.length; i++) {
			if (manager[i] == -1) {
				root = i;
			} else
				indexs[manager[i]].add(i);
		}
		Queue<int[]> queue = new LinkedList<>();
		queue.add(new int[] { root, 0 });
		int ans = 0;
		while (!queue.isEmpty()) {
			int[] cur = queue.poll();
			int f = cur[0], t = cur[1], it = t + informTime[f];
			ans = Math.max(ans, t);
			List<Integer> next = indexs[cur[0]];
			for (int nxt : next) {
				queue.add(new int[] { nxt, it });
			}
		}
		return ans;
	}
}
